
class TreeNode {
    constructor(data) {
        this.data = data;
        this.height = 0;
        this.right = null;
        this.left = null;
    }
    //获得结点的平衡因子
    getBalance(){
        let left =  (this.left==null ? 0:this.left.height);
        let right = (this.right==null ? 0:this.right.height);
        return left - right;
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }
    /*
     * 获取树的高度
     */
    height(node) {
        if (node != null)
            return node.height;

        return 0;
    }

    _height() {
        return this.height(this.root);
    }

    //查找结点
    search(node, data) {
        while (node!=null) {
            if (data < node.data)
                node = node.left;
            else if (data > node.data)
                node = node.right;
            else
                return node;
        }
        return node;
    }

    //左左局面旋转
    leftLeftRotation(node) {
        //leftChildNode 对应示意图中的结点B
        let leftChildNode = node.left;
        node.left = leftChildNode.right;
        leftChildNode.right = node;
        //刷新结点A和结点B的高度
        node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
        leftChildNode.height = Math.max(this.height(leftChildNode.left), node.height) + 1;
        //返回旋转后的父结点
        return leftChildNode;
    }

    //右右局面旋转
    rightRightRotation(node) {
        //rightChildNode 对应示意图中的结点B
        let rightChildNode = node.right;
        node.right = rightChildNode.left;
        rightChildNode.left = node;
        //刷新结点A和结点B的高度
        node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
        rightChildNode.height = Math.max(this.height(rightChildNode.right), node.height) + 1;
        //返回旋转后的父结点
        return rightChildNode;
    }

    //左右局面旋转
    leftRightRotation(node) {
        //先做左旋
        node.left = this.rightRightRotation(node.left);
        //再做右旋
        return this.leftLeftRotation(node);
    }

    //右左局面旋转
    rightLeftRotation(node) {
        //先做右旋
        node.right = this.leftLeftRotation(node.right);
        //再做左旋
        return this.rightRightRotation(node);
    }

    //插入结点
    _insert(data) {
        this.root = this.insert(this.root, data);
    }

    //插入结点详细过程（递归）
    insert(node, data) {
        if (node == null) {
            node = new TreeNode(data);
        } else {
            if (data < node.data) {
                //新结点小于当前结点，选择当前结点的左子树插入
                node.left = this.insert(node.left, data);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (node.getBalance() == 2) {
                    if (data < node.left.data) {
                        node = this.leftLeftRotation(node);
                    } else {
                        node = this.leftRightRotation(node);
                    }
                }
            } else if (data > node.data)  {
                //新结点大于当前结点，选择当前结点的右子树插入
                node.right = this.insert(node.right, data);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (node.getBalance() == -2) {
                    if (data > node.right.data) {
                        node = this.rightRightRotation(node);
                    } else {
                        node = this.rightLeftRotation(node);
                    }
                }
            } else {
                console.log("AVL树中已有重复的结点！");
            }
        }
        //刷新结点的高度
        node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
        return node;
    }

    //删除结点
    _remove(data) {
        let deletedNode;
        if ((deletedNode = this.search(this.root, data)) != null)
            this.root = this.remove(this.root, deletedNode);
    }

    //删除结点详细过程（递归）
    remove( node, deletedNode) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (node==null || deletedNode==null)
            return null;
        if (deletedNode.data < node.data){
            //待删除结点小于当前结点，在当前结点的左子树继续执行
            node.left = this.remove(node.left, deletedNode);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (this.height(node.right) - this.height(node.left) == 2) {
                let r =  node.right;
                if (this.height(r.left) > this.height(r.right))
                    node = this.rightLeftRotation(node);
                else
                    node = this.rightRightRotation(node);
            }
        } else  if (deletedNode.data > node.data) {
            //待删除结点大于当前结点，在当前结点的右子树继续执行
            node.right = this.remove(node.right, deletedNode);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (this.height(node.left) - this.height(node.right) == 2) {
                let l =  node.left;
                if (this.height(l.right) > this.height(l.left))
                    node = this.leftRightRotation(node);
                else
                    node = this.leftLeftRotation(node);
            }
        } else {
            // tree的左右孩子都非空
            if ((node.left!=null) && (node.right!=null)) {
                if (this.height(node.left) > this.height(node.right)) {
                    // 如果node的左子树比右子树高，找出左子树最大结点赋值给Node，并删除最小结点
                    let max = this.maximum(node.left);
                    node.data = max.data;
                    node.left = this.remove(node.left, max);
                } else {
                    // 如果node的右子树比左子树高，找出右子树最小结点赋值给Node，并删除最小结点
                    let min = this.minimum(node.right);
                    node.data = min.data;
                    node.right = this.remove(node.right, min);
                }
            } else {
                node = (node.left!=null) ? node.left : node.right;
            }
        }
        node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
        return node;
    }

    //找出结点node为根的子树的最大节点
    maximum(node) {
        if (node == null)
            return null;
        while(node.right != null)
            node = node.right;
        return node;
    }

    //找出结点node为根的子树的最小节点
    minimum(node) {
        if (node == null)
            return null;
        while(node.left != null)
            node = node.left;
        return node;
    }

    //中序遍历
    static inOrderTraversal(node) {
        if(node != null) {
            AVLTree.inOrderTraversal(node.left);
            console.log(node.data+" ");
            AVLTree.inOrderTraversal(node.right);
        }
    }

    //层序遍历
    static  levelOrderTraversal(root){
        let queue = [];
        queue.push(root);
        while(queue.length){
            let node = queue.shift();
            console.log(node.data+" ");
            if(node.left != null){
                queue.push(node.left);
            }
            if(node.right != null){
                queue.push(node.right);
            }
        }
    }
}


    let tree = new AVLTree();
    let input= [5,3,7,2,4,6,9,1];
    for(let i=0; i<input.length; i++) {
        tree._insert(input[i]);
    }
    console.log("中序遍历: ");
    AVLTree.inOrderTraversal(tree.root);
    console.log("层序遍历: ");
    AVLTree.levelOrderTraversal(tree.root);
    
    console.log("高度: %d\n", tree._height());
    let deletedData = 3;

    console.log("删除根节点: %d\n", deletedData);
    tree._remove(deletedData);

    console.log("中序遍历: ");
    AVLTree.inOrderTraversal(tree.root);
    console.log("层序遍历: ");
    AVLTree.levelOrderTraversal(tree.root);
    console.log("高度: %d\n", tree._height());
